import org.junit.Test;

import java.util.*;


// 拓扑排序
// 如果存在环，就无法进行拓扑排序
public class TopologicalSort {
    public static void main(String[] args) {
        Vertex v1 = new Vertex("网页基础");
        Vertex v2 = new Vertex("Java基础");
        Vertex v3 = new Vertex("JavaWeb");
        Vertex v4 = new Vertex("Spring框架");
        Vertex v5 = new Vertex("微服务框架");
        Vertex v6 = new Vertex("数据库");
        Vertex v7 = new Vertex("实战项目");

        v1.edges = List.of(new Edge(v3)); // +1
        v2.edges = List.of(new Edge(v3)); // +1
        v3.edges = List.of(new Edge(v4));
        v6.edges = List.of(new Edge(v4));
        v4.edges = List.of(new Edge(v5));
        v5.edges = List.of(new Edge(v7));
        v7.edges = List.of();

        List<Vertex> graph = List.of(v1, v2, v3, v4, v5, v6);
        LinkedList<String> result = new LinkedList<>();
        for (Vertex v : graph) {
            if (v.status == 0) {
                dfs(v, result);
            }
        }
        System.out.println(result);

        toPoSort(graph);

        Vertex v8 = new Vertex("v1");
        Vertex v9 = new Vertex("v2");
        Vertex v10 = new Vertex("v3");
        Vertex v11 = new Vertex("v4");
        Vertex v12 = new Vertex("v5");
        Vertex v13 = new Vertex("v6");

        v8.edges = List.of(new Edge(v10, 9), new Edge(v9, 7), new Edge(v13, 14));
        v9.edges = List.of(new Edge(v11, 15));
        v10.edges = List.of(new Edge(v11, 11), new Edge(v13, 2));
        v11.edges = List.of(new Edge(v12, 6));
        v12.edges = List.of();
        v13.edges = List.of(new Edge(v12, 9));

        List<Vertex> graph2 = List.of(v8, v9, v10, v11, v12, v13);
        dijkstra(graph2, v8);

        dijkstra2(graph2, v8);


    }

    @Test
    public void BellmanFord(){

        // 负环情况
//        Vertex v1 = new Vertex("v1");
//        Vertex v2 = new Vertex("v2");
//        Vertex v3 = new Vertex("v3");
//        Vertex v4 = new Vertex("v4");
//
//        v1.edges = List.of(new Edge(v2, 2));
//        v2.edges = List.of(new Edge(v3, -4));
//        v3.edges = List.of(new Edge(v4, 1), new Edge(v1, 1));
//        v4.edges = List.of();
//        List<Vertex> graph = List.of(v1, v2, v3, v4);


        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");
        Vertex v5 = new Vertex("v5");
        Vertex v6 = new Vertex("v6");

        v1.edges = List.of(new Edge(v3, 9), new Edge(v2, 7), new Edge(v6, 14));
        v2.edges = List.of(new Edge(v4, 15));
        v3.edges = List.of(new Edge(v4, 11), new Edge(v6, 2));
        v4.edges = List.of(new Edge(v5, 6));
        v5.edges = List.of();
        v6.edges = List.of(new Edge(v5, 9));



        List<Vertex> graph = List.of(v4, v5, v6, v1, v2, v3);
//        bellmanFord(graph, v1);

    }

    private static void toPoSort(List<Vertex> graph) {
        // 1. 统计每个顶点的入度
        for (Vertex v : graph){
            for (Edge edge : v.edges) {
                edge.linked.inDegree++;
            }
        }

        // 2. 将入度为0的顶点加入队列
        LinkedList<Vertex> queue = new LinkedList<>();
        for (Vertex v : graph){
            if (v.inDegree == 0){
                queue.offer(v);
            }
        }

        // 3. 队列中不断移除顶点，每移除一个顶点，把它相邻顶点入度减1，若减到0则入队
        List<String> result = new ArrayList<>();
        while (!queue.isEmpty()){
            Vertex ver = queue.poll();
            result.add(ver.name);
            for (Edge edge : ver.edges){
                edge.linked.inDegree--;
                if (edge.linked.inDegree == 0){
                    queue.offer(edge.linked);
                }
            }
        }
        // 判断是否存在环
        if (result.size() == graph.size()){
            for (String key : result){
                System.out.println(key);
            }
        }else {
            System.out.println("存在环");
        }
    }

    // DFS:拓扑排序深度优先遍历
    public static void dfs(Vertex v, LinkedList<String> result){
        if (v.status == 2){
            return;
        }
        if (v.status == 1){
            throw new RuntimeException("存在环，无法进行排序");
        }
        v.status = 1;
        for (Edge edge : v.edges){
            dfs(edge.linked, result);
        }
        v.status = 2;
        result.push(v.name);
    }

    // 最短路径
    // Dijkstra算法
     /*
    算法描述：
        1. 将所有顶点标记为未访问。创建一个未访问顶点的集合。
        2. 为每个顶点分配一个临时距离值
           * 对于我们的初始顶点，将其设置为零
           * 对于所有其他顶点，将其设置为无穷大。
        3. 每次选择最小临时距离的未访问顶点，作为新的当前顶点
        4. 对于当前顶点，遍历其所有未访问的邻居，并更新它们的临时距离为更小
           * 例如，1->6 的距离是 14，而1->3->6 的距离是11。这时将距离更新为 11
           * 否则，将保留上次距离值
        5. 当前顶点的邻居处理完成后，把它从未访问集合中删除
     */
    private static void dijkstra(List<Vertex> graph, Vertex resuorce) {
        List<Vertex> list = new ArrayList<>(graph);
        resuorce.dist = 0;
        while (!list.isEmpty()){
            // 3. 选取当前顶点
            Vertex ver = chooseMinDistVertex(list);
            // 4. 更新当前顶点邻居距离
            updateNeighboursDist(ver, list);
            // 5. 移除当前顶点
            list.remove(ver);
            ver.visited = true;
        }

        for (Vertex v : graph) {
            System.out.println(v.name + " " + v.dist + "  " + (v.prev == null ? null : v.prev.name));
        }
    }

    private static void updateNeighboursDist(Vertex ver, List<Vertex> list) {
        for (Edge edge : ver.edges){
            Vertex n = edge.linked;
            // if判断条件也可以改为 (!n.visited) 此时可以删除list参数,提高效能
            if (list.contains(n)){
                int dist = edge.weight + ver.dist;
                if (dist < n.dist){
                    n.dist = dist;
                    n.prev = ver;
                }
            }
        }
    }

    private static Vertex chooseMinDistVertex(List<Vertex> list) {
        Vertex min = list.get(0);
        for (int i = 1; i < list.size(); i++){
            if (min.dist > list.get(i).dist){
                min = list.get(i);
            }
        }
        return min;
    }

    // 改进,用优先级队列实现
    private static void dijkstra2(List<Vertex> graph, Vertex resuorce) {
        PriorityQueue<Vertex> queue = new PriorityQueue<>(Comparator.comparingInt(v->v.dist));
        resuorce.dist = 0;
        for (Vertex v : graph){
            queue.offer(v);
        }
        while (!queue.isEmpty()){
            // 3. 选取当前顶点
            Vertex ver = queue.peek();
            // 4. 更新当前顶点邻居距离
            if (!ver.visited) {
                updateNeighboursDist2(ver, queue);
                ver.visited = true;
            }
            // 5. 移除当前顶点
            queue.poll();
        }

        for (Vertex v : graph) {
            System.out.println(v.name + " " + v.dist + "  " + (v.prev == null ? null : v.prev.name));
        }
    }

    private static void updateNeighboursDist2(Vertex ver, PriorityQueue<Vertex> list) {
        for (Edge edge : ver.edges){
            Vertex n = edge.linked;
            // if判断条件也可以改为 (!n.visited) 此时可以删除list参数,提高效能
            if (list.contains(n)){
                int dist = edge.weight + ver.dist;
                if (dist < n.dist){
                    n.dist = dist;
                    n.prev = ver;
                }
            }
        }
    }

    // BellmanFord算法
    public static void bellmanFord(List<Vertex> graph, Vertex v){
        v.dist = 0;
        int size = graph.size();
        // 记录每一轮中是否发生更新
        boolean updated = true;
        // 1. 进行 顶点个数 - 1 轮处理
        for (int i = 0; i < size - 1 && updated; i++){
            updated = false;
            // 2. 遍历所有的边
            for (Vertex s : graph){
                for (Edge edge : s.edges){
                    // 3. 处理每一条边
                    Vertex e = edge.linked;
                    if (s.dist != Integer.MAX_VALUE && e.dist > s.dist + edge.weight){
                        e.dist = s.dist + edge.weight;
                        e.prev = s;
                        updated = true;
                    }
                }
            }
        }
        // 检查每一轮处理结束后，是否还有节点发生更新
        if (updated) {
            throw new RuntimeException("有环");
        } else {
            for (Vertex vertex : graph) {
                System.out.println(vertex.name + " " + (vertex.prev != null ? vertex.prev.name : "null"));
            }
        }
    }



}
